Как и алгоритм поиска A*, RBFS является оптимальным алгоритмом, если эвристическая функция h(n) допустима. Его пространственная сложность равна 0{bd), но охарактеризовать временную сложность довольно трудно: она зависит и от точности эвристической функции, и от того, насколько часто происходила смена наилучшего пути по мере развертывания узлов. И алгоритм IDA*, и алгоритм RBFS подвержены потенциальному экспоненциальному увеличению сложности, связанной с поиском в графах (см. раздел 3.5), поскольку эти алгоритмы не позволяют определять наличие повторяющихся состояний, отличных от тех, которые находятся в текущем пути. Поэтому данные алгоритмы способны много раз исследовать одно и то же состояние.

Алгоритмы IDA* и RBFS страдают от того недостатка, что в них используется слишком мало памяти. Между итерациями алгоритм IDA* сохраняет только единственное число — текущий предел f-стоимости. Алгоритм RBFS сохраняет в памяти больше информации, но количество используемой в нем памяти измеряется лишь значением O(bd): даже если бы было доступно больше памяти, алгоритм RBFS не способен ею воспользоваться.

Поэтому представляется более разумным использование всей доступной памяти. Двумя алгоритмами, которые осуществляют это требование, являются поиск МА* (Memory-bounded А* — поиск А* с ограничением памяти) и SMA* (Simplified MA* — упрощенный поиск МА*). В данном разделе будет описан алгоритм SMA*, который действительно является более простым, чем другие алгоритмы этого типа. Алгоритм SMA* действует полностью аналогично поиску А*, развертывая наилучшие листовые узлы до тех пока, пока не будет исчерпана доступная память. С этого момента он не может добавить новый узел к дереву поиска, не уничтожив старый. В алгоритме SMA* всегда уничтожается наихудший листовой узел (тот, который имеет наибольшее f-значение). Как и в алгоритме RBFS, после этого в алгоритме SMA* значение забытого (уничтоженного) узла резервируется в его родительском узле. Благодаря этому предок забытого поддерева позволяет определить качество наилучшего пути в этом поддереве. Поскольку имеется данная информация, в алгоритме SMA* поддерево восстанавливается, только если обнаруживается, что все другие пути выглядят менее многообещающими по сравнению с забытым путем. Иными словами, если все потомки узла п забыты, то неизвестно, каким путем можно следовать от л, но все еще можно получить представление о том, есть ли смысл куда-либо следовать от п.